package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 层级遍历二叉树，返回 int[1,3,2,...] 形式
 * 
 * 考察点：
 *      二叉树的层级遍历
 *      
 *      队列的常用方法：添加元素、获取并删除元素、获取元素；创建一个队列
 *            创建一个队列：可使用 LinkedList()
 *            队列的常用方法对比
 *                    返回特殊值 / 抛出异常
 *                添加：offer() / add()
 *                移除：poll() / remove()
 *                检查：peek() / element()
 *      
 *      ArrayList<Integer> 转 int[]
 *          直接 新建一个 int[] 逐个复制
 *          使用steam mapToInt toArray()
 */
public class _32_1_从上到下打印二叉树 {
    @Test
    public void main(String[] args) {
        Integer[] input = new Integer[]{3, 9, 20, null, null, 15, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        int[] result = levelOrder(root);
        System.out.println(Arrays.toString(result));
    }
    
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
    
        List<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        return ans.stream().mapToInt(Integer::valueOf).toArray();
    }
}
